#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// continuous ints sum up to n
void print_sum(size_t small, size_t big) {
  if (small > big)
    return;

  for (size_t i = small; i <= big; i++) {
    cout << i << " ";
  }
  cout << endl;
}

void ints_sum_up_to_n(size_t n) {
  if (n < 3)
    return;

  size_t small = 1;
  size_t big = 2;
  size_t sum = 3;

  while (small < big) {
    if (sum == n) {
      print_sum(small, big);
      sum -= small;
      small++;
    }
    else if (sum < n) {
      big++;
      sum += big;
    }
    else {
      sum -= small;
      small++;
    }
  }
}

// find ugly numbers
// factors (2,3,5); 1 is the first ugly number
size_t ugly_num(size_t n) {
  vector<size_t> uglynums(n, 0);
  uglynums[0] = 1;

  size_t two_p = 0;
  size_t three_p = 0;
  size_t five_p = 0;
  
  for (size_t p = 1; p < n; p++) {
    size_t nums[] = {uglynums[two_p] * 2, uglynums[three_p] * 3, uglynums[five_p] * 5};
    uglynums[p] = *min_element(nums, nums+3);

    while (uglynums[two_p] * 2 <= uglynums[p])
      two_p++;
    while (uglynums[three_p] * 3 <= uglynums[p])
      three_p++;
    while (uglynums[five_p] * 5 <= uglynums[p])
      five_p++;
  }

  return uglynums[n-1];
}

// print 1 to n digit max nums
void print_one_to_max_n_rec(char* output, size_t n, size_t output_pos, size_t input_pos, bool set_leading) {
  if (input_pos == n) {
    cout << output << endl;
    return;
  }

  // don't choose any digit
  if (! set_leading) {
    print_one_to_max_n_rec(output, n, output_pos, input_pos+1, false);
  }
  
  // not leading digit
  if (set_leading) {
    output[output_pos] = '0';
    print_one_to_max_n_rec(output, n, output_pos+1, input_pos+1, true);
    output[output_pos] = '\0';
  }
  
  for (char p = '1'; p <= '9'; p++) {
    output[output_pos] = p;
    print_one_to_max_n_rec(output, n, output_pos+1, input_pos+1, true);
    output[output_pos] = '\0';
  }
}

void print_one_to_max_n(size_t n) {
  char* output = new char[n+1];
  memset(output, '\0', n+1);
  
  print_one_to_max_n_rec(output, n, 0, 0, false);

  delete [] output;
}

// form min number
int compare(const char* str1, const char* str2) {
  size_t len1 = strlen(str1);
  size_t len2 = strlen(str2);

  size_t len = len1 + len2 + 1;
  char* op1 = new char[len];
  char* op2 = new char[len];

  memset(op1, '\0', len);
  memcpy(op1, str1, len1);
  memcpy(op1+len1, str2, len2);

  memset(op2, '\0', len);
  memcpy(op2, str2, len2);
  memcpy(op2+len2, str1, len1);

  int ret = strcmp(op1, op2);

  delete [] op1;
  delete [] op2;

  return ret;
}

void form_min_num(char** arr, size_t len) {
  if (!arr)
    return;

  sort(arr, arr+len, compare);
  for (size_t i = 0; i < len; i++) {
    cout << arr[i];
  }
  cout << endl;
}

// n-dices sum and its probability
void print_dices_sum_prob(size_t n) {
  
}

// add without arithmetic
int add(int a, int b) {
  if (b == 0) {
    return a;
  }

  int sum = a ^ b;
  int carry = (a & b) << 1;

  return add(sum, carry);
}

int add_addr(int a, int b) {
  char* c = (char*) a;
  return (int) &c[b];
}

int main() {
  cout << "Test continuous ints that sum up to n" << endl;
  ints_sum_up_to_n(15);

  cout << "Test nth ugly number: " << ugly_num(10) << endl;
  cout << "Test nth ugly number: " << ugly_num(1500) << endl;

  cout << "Test print 1 to max n digit numbers" << endl;
  print_one_to_max_n(2);  // print 1,2,..,99

  cout << "Test form min number from array" << endl;
  char* ints[] = {"32", "321"};
  form_min_num(ints, sizeof(ints)/sizeof(char*));
 
  cout << "Test n dices sums and their probabilities" << endl;
  print_dices_sum_prob(2);

  cout << "Test without arithmetic ops: " << add(13, 5) << endl;
  cout << "Test without arithmetic ops: " << add_addr(13, 5) << endl;

  return 0;
}
